991C - Candies - CodeForces Solution

def solveDQ(state, base_cases, get_sub_problems, merge):
  for condition, result in base_cases:
    if condition(state):
      return result(state)
  
  sub_problems = get_sub_problems(state)

  sub_results = [
    solveDQ(sub_problem, base_cases, get_sub_problems, merge) 
    for sub_problem in sub_problems
  ]

  result = merge(sub_results)

  return result

def binary_search_first_high(l, r, condition):
  def get_sub_problems(state):
        l, r = state
    mid = (l + r) // 2
    if condition(mid):
      return [(l, mid)]
    else:
      return [(mid + 1, r)]

  state = (l, r)
  base_cases = [(lambda s: s[0] == s[1], lambda s: s[0])]
  merge = lambda sub_results: sub_results[0]
  return solveDQ(
    state,
    base_cases,
    get_sub_problems,
    merge,
  )

if __name__ == "__main__":
  n = int(input())

  def isValid(n):
    def condition(mid):
      taken = 0
      nonlocal n
      base = n
      while(base):
        portion = base if base <= mid else mid
        taken += portion
        base -= portion
        base -= base // 10
      return 2 * taken >= n
    return condition

  print(binary_search_first_high(1, n, isValid(n)))